package trackClustering.example.spatial;

import trackClustering.example.entity.TrajectoryPoint;

import java.util.*;
import java.util.stream.Collectors;

public class TrajectoryProcessByHdbascan {
    private final int minPts;
    private final int minClusterSize;
    private Map<TrajectoryPoint, Double> coreDistances;
    private List<ClusterNode> clusterTree;
    private List<TrajectoryPoint> points;
    
    // 双参数构造器
    public TrajectoryProcessByHdbascan(int minPts, int minClusterSize) {
        if(minPts < 2) {
            throw new IllegalArgumentException("minPts必须大于等于2");
        }
        if(minClusterSize < minPts) {
            throw new IllegalArgumentException("minClusterSize不能小于minPts");
        }
        this.minPts = minPts;
        this.minClusterSize = minClusterSize;
    }

    public Map<Integer, List<TrajectoryPoint>> cluster(List<TrajectoryPoint> points) {
        this.points = points;
        calculateCoreDistances();
        double[][] mutualReachability = buildMutualReachabilityMatrix();
        List<Edge> mst = buildMinimumSpanningTree(mutualReachability);
        buildClusterHierarchy(mst);
        return extractStableClusters();
    }
    private void calculateCoreDistances() {
        coreDistances = new HashMap<>();
        // 修复k值计算逻辑，增加动态调整
        int k = Math.max(1, Math.min(minPts, points.size()/2));  // 确保k≥1
        
        for (TrajectoryPoint point : points) {
            List<Double> distances = points.stream()
                .filter(p -> !p.equals(point))
                .map(p -> calculateDistance(point, p))
                .sorted()
                .collect(Collectors.toList());
            
            // 添加距离缩放因子
            double scalingFactor = 1.0 + (new Random().nextDouble() * 0.001); // 添加0.1%随机扰动
            double coreDistance = distances.isEmpty() ? 0.0 : 
                (k < distances.size()) ? distances.get(k) * scalingFactor : 
                distances.get(distances.size()-1) * scalingFactor;
            coreDistances.put(point, coreDistance);
        }
    }

    private double[][] buildMutualReachabilityMatrix() {
        int size = points.size();
        double[][] matrix = new double[size][size];
        
        for (int i = 0; i < size; i++) {
            TrajectoryPoint p1 = points.get(i);
            for (int j = i + 1; j < size; j++) {
                TrajectoryPoint p2 = points.get(j);
                double distance = calculateDistance(p1, p2);
                matrix[i][j] = matrix[j][i] = Math.max(
                    Math.max(coreDistances.get(p1), coreDistances.get(p2)), 
                    distance
                );
            }
        }
        return matrix;
    }

    private List<Edge> buildMinimumSpanningTree(double[][] matrix) {
        List<Edge> edges = new ArrayList<>();
        int n = matrix.length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                edges.add(new Edge(i, j, matrix[i][j]));
            }
        }
        edges.sort(Comparator.comparingDouble(e -> e.weight));
        
        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();
        
        for (Edge edge : edges) {
            if (uf.find(edge.from) != uf.find(edge.to)) {
                mst.add(edge);
                uf.union(edge.from, edge.to);
            }
        }
        return mst;
    }
    private void buildClusterHierarchy(List<Edge> mst) {
        mst.sort(Comparator.comparingDouble(e -> -e.weight));
        UnionFind uf = new UnionFind(points.size());
        clusterTree = new ArrayList<>();
        
        // 新增：维护节点映射表
        Map<Integer, ClusterNode> nodeMap = new HashMap<>();
        
        for (Edge edge : mst) {
            int root1 = uf.find(edge.from);
            int root2 = uf.find(edge.to);
            
            if (root1 != root2) {
                // 添加合并阈值检查
                if (1.0/edge.weight < Math.max(
                    coreDistances.get(points.get(root1)),
                    coreDistances.get(points.get(root2))) * 1.5) {
                    
                    // 添加子节点获取逻辑
                    ClusterNode child1 = nodeMap.getOrDefault(root1, null);
                    ClusterNode child2 = nodeMap.getOrDefault(root2, null);
                    
                    ClusterNode node = new ClusterNode(
                        uf.getClusterSize(root1),
                        uf.getClusterSize(root2),
                        1.0 / edge.weight,
                        edge,
                        uf.getMembers(root1),
                        uf.getMembers(root2),
                        child1,
                        child2
                    );
                    clusterTree.add(node);
                    uf.union(root1, root2);
                    nodeMap.put(uf.find(root1), node);
                }
            }
        }
    }
    private Map<Integer, List<TrajectoryPoint>> extractStableClusters() {
        // 修改点：使用唯一节点ID替代哈希码
        Map<Integer, Double> stabilityScores = new HashMap<>();
        int nodeCounter = 0;
        Map<ClusterNode, Integer> nodeIds = new IdentityHashMap<>();
        
        // 修改点：逆向遍历clusterTree确保父节点优先处理
        List<ClusterNode> processingOrder = new ArrayList<>(clusterTree);
        Collections.reverse(processingOrder);  // 反转处理顺序
        
        for (ClusterNode node : processingOrder) {  // 使用逆向顺序
            nodeIds.put(node, ++nodeCounter);
            double deltaLambda = node.parent == null ? 
                node.lambda : node.parent.lambda - node.lambda;
            
            stabilityScores.merge(nodeCounter, node.members.size() * deltaLambda, Double::sum);
            
            // 添加空安全检查
            if (node.parent != null && nodeIds.containsKey(node.parent)) {
                int parentId = nodeIds.get(node.parent);
                stabilityScores.merge(parentId, -node.members.size() * deltaLambda, Double::sum);
            }
        }
    
        // 修改点：增加密度过滤条件
        List<ClusterNode> validClusters = clusterTree.stream()
            .filter(node -> node.members.size() >= minClusterSize)
            .filter(node -> stabilityScores.getOrDefault(nodeIds.get(node), 0.0) > 0)
            .sorted((n1, n2) -> Double.compare(
                stabilityScores.get(nodeIds.get(n2)),
                stabilityScores.get(nodeIds.get(n1))))
            .collect(Collectors.toList());
        
        Map<Integer, List<TrajectoryPoint>> result = new HashMap<>();
        int clusterId = 0;
        Set<Integer> assigned = new HashSet<>();
        
        for (ClusterNode node : validClusters) {
            List<TrajectoryPoint> clusterPoints = new ArrayList<>();
            
            // 修改点：使用有序遍历并添加未分配的点
            node.members.stream()
                .sorted()
                .forEach(index -> {
                    if (!assigned.contains(index)) {
                        clusterPoints.add(points.get(index));
                        assigned.add(index);
                    }
                });
            
            if (!clusterPoints.isEmpty()) {
                result.put(++clusterId, clusterPoints);
            }
        }
        return result;
    }

    private ClusterNode findChildCluster(int root) {
        return clusterTree.stream()
            .filter(n -> n.children.stream().anyMatch(c -> c.members.contains(root)))
            .findFirst()
            .orElse(null);
    }

    private double calculateDistance(TrajectoryPoint p1, TrajectoryPoint p2) {
        double deltaX = p2.getEasting() - p1.getEasting();
        double deltaY = p2.getNorthing() - p1.getNorthing();
        double heightDifference = (p1.getHeight() - p2.getHeight());
        return Math.sqrt(Math.pow(deltaX, 2) + Math.pow(deltaY, 2) + Math.pow(heightDifference, 2));
    }

    // 以下内部类保持不变
    private static class Edge {
        final int from;
        final int to;
        final double weight;

        Edge(int from, int to, double weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    private class ClusterNode {
        // 改用LinkedHashSet保持插入顺序
        final Set<Integer> members = new LinkedHashSet<>(); 
        final int size;
        final double lambda;
        final Edge edge;
        final List<ClusterNode> children = new ArrayList<>();
        ClusterNode parent;
    
        ClusterNode(int size1, int size2, double lambda, Edge edge, 
                   List<Integer> members1, List<Integer> members2,
                   ClusterNode child1, ClusterNode child2) {
            // 保持成员添加顺序（移除重复初始化）
            this.members.addAll(members1);
            this.members.addAll(members2);
            this.size = size1 + size2;
            this.lambda = lambda;
            this.edge = edge;
            
            if (child1 != null) {
                children.add(child1);
                child1.parent = this;
            }
            if (child2 != null) {
                children.add(child2);
                child2.parent = this;
            }
        }
    }
    private class UnionFind {
        private final int[] parent;
        private final int[] rank;
        private final int[] size;
        private final Map<Integer, List<Integer>> members;
    
        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            size = new int[n];
            members = new HashMap<>();
            
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
                size[i] = 1;
                members.put(i, new ArrayList<>(Collections.singletonList(i)));
            }
        }
    
        int find(int x) {
            // 路径压缩优化
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    
        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) return;
    
            // 按秩合并优化
            if (rank[rootX] > rank[rootY]) {
                mergeClusters(rootX, rootY);
            } else if (rank[rootX] < rank[rootY]) {
                mergeClusters(rootY, rootX);
            } else {
                mergeClusters(rootX, rootY);
                rank[rootY]++;
            }
        }
    
        private void mergeClusters(int largerRoot, int smallerRoot) {
            parent[smallerRoot] = largerRoot;
            size[largerRoot] += size[smallerRoot];
            members.get(largerRoot).addAll(members.get(smallerRoot));
            members.remove(smallerRoot);
        }
    
        int getClusterSize(int root) {
            return size[root];
        }
    
        List<Integer> getMembers(int root) {
            return members.getOrDefault(root, Collections.emptyList());
        }
    }
}